package com.algorithm;

import java.util.Arrays;

public class Quicksort {
    private void quickSort(int[] nums, int left, int right) {
        if (left < right) {
            int idx = getIndex(nums, left, right);
            quickSort(nums, left, idx - 1);
            quickSort(nums, idx + 1, right);
        }
    }

    private int getIndex(int[] nums, int left, int right) {
        int tmp = nums[left];
        while (left < right) {
            while(left < right && nums[right] >= tmp) {
                right--;
            }
            nums[left] = nums[right];

            while(left < right && nums[left] <= tmp) {
                left++;
            }
            nums[right] = nums[left];
        }
        nums[left] = tmp;

        return left;
    }

    public static void main(String[] args) {
        int[] nums = {9, 3, 6, 2, 10, 8, 4, 5, 7};
        new Quicksort().quickSort(nums, 0, nums.length - 1);

        for (int num : nums) {
            System.out.print(num + ",");
        }
    }
}
